#include <iostream>
#include <cstdlib>
using namespace std;
/* 
    带头结点的单链表非递减有序，
    设计算法删除表中重复的多余元素，
    同时释放被删除的结点
*/
typedef struct lnode
{
    int data;
    struct lnode *next;
} lnode, *linklist;

// 尾插法建立单链表
void createlist(linklist &l)
{
    lnode *r, *s;
    l = (lnode *)malloc(sizeof(lnode));
    l->next = nullptr;
    r = l;
    int x;
    cout << "输入元素,空格分割，999结束" << endl;
    cin >> x;
    while (x != 999)
    {
        // 新建结点
        s = (lnode *)malloc(sizeof(lnode));
        s->next = nullptr;
        s->data = x;
        // 插入结点
        r->next = s;
        r = s;
        cin >> x;
    }
    r = nullptr;
}
void printlist(linklist l)
{
    lnode *p = l->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
        /* code */
    }
    cout << endl;
}
// 去重
/* 
算法思想设置p作为工作指针向后扫描的比较p和p的后继r是否相等
若相等则需要删除r达到去重的目的， */
void dedup(linklist &l)
{
    lnode *p = l->next, *r;
    while (p->next)
    {
        r = p->next;
        if (p->data == r->data)
        {
            // p指向r的后继
            p->next = r->next;

            // 释放待删除的结点
            free(r);
            /* code */
        }
        p = p->next;
        /* code */
    }
}
int main(int argc, char const *argv[])
{
    linklist l;
    createlist(l);
    printlist(l);
    dedup(l);
    printlist(l);
    return 0;
}
